TNotes.leetcode

Appearance

0872. 叶子相似的树【简单】

0872. 叶子相似的树【简单】 ​

1. 📝 题目描述 ​

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列。

img

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false。

示例 1：

img

txt
输入：
root1 = [3,5,1,6,2,9,8,null,null,7,4],
root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

输出：true

示例 2：

img

txt
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

提示：

  • 给定的两棵树结点数在 [1, 200] 范围内
  • 给定的两棵树上的值在 [0, 200] 范围内

2. 🎯 s.1 - 深度优先搜索（DFS） ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function (root1, root2) {
  // 获取树的叶值序列
  const getLeafValues = (root, leaves) => {
    if (!root) return

    // 如果是叶子节点，将值加入序列
    if (!root.left && !root.right) {
      leaves.push(root.val)
      return
    }

    // 递归遍历左右子树
    getLeafValues(root.left, leaves)
    getLeafValues(root.right, leaves)
  }

  // 分别获取两棵树的叶值序列
  const leaves1 = []
  const leaves2 = []

  getLeafValues(root1, leaves1)
  getLeafValues(root2, leaves2)

  // 比较两个叶值序列是否相同
  if (leaves1.length !== leaves2.length) {
    return false
  }

  for (let i = 0; i < leaves1.length; i++) {
    if (leaves1[i] !== leaves2[i]) {
      return false
    }
  }

  return true
}
  • 时间复杂度：O(T1+T2)，其中 T1 和 T2 分别是两棵树的节点数，需要遍历两棵树
  • 空间复杂度：O(T1+T2)，需要存储两棵树的叶值序列以及递归调用栈的空间
  • 算法思路：
    1. 获取叶值序列：通过深度优先搜索（DFS）遍历二叉树，收集所有叶子节点的值
    2. 判断叶子节点：当一个节点既没有左子树也没有右子树时，它就是叶子节点
    3. 比较序列：将两棵树的叶值序列进行比较，如果长度不同或对应位置的值不同，则不相似

Discussions